// 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

// 最近公共祖先的定义为：
// “对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
// 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

// 说明:
// 所有节点的值都是唯一的。
// p、q 为不同节点且均存在于给定的二叉搜索树中。

const lowestCommonAncestor = function (root: TreeNode | null,
    p: TreeNode, q: TreeNode): TreeNode | null {
    // 安全检测
    if (root === null) {
        return null;
    }
    const rootValue: number = root.val
    // 如果p\q值均大于根节点，则递归遍历右子树
    if (p.val > rootValue && q.val > rootValue) {
        return lowestCommonAncestor(root.right, p, q);
    }
    // 如果p\q值均小于于根节点，则递归遍历左子树
    else if (p.val < rootValue && q.val < rootValue) {
        return lowestCommonAncestor(root.left, p, q);
    }
    // 其他情况返回根节点
    else {
        return root;
    }
};

// 本题其实类似于一道例题，大可以完全当作是相关性质记录下来
// 首先二叉搜索树最经典的性质包含：
// 1. 中序遍历的结果是一个升序数组·
// 2. 所有比根节点小的值都位于左子树，比根节点大的值都位于右子树
// 这里主要用到的是第二条性质
// 首先我们使用深度优先遍历的框架，
// 如果 p 和 q 的值均小于当前根节点
// 说明 p 和 q 均位于根节点左子树
// 如果 p 和 q 的值均大于当前根节点
// 说明 p 和 q 均位于根节点右子树
// 我们根据情况对左右子树进行遍历
// 直到最后的剩余情况
// 如果一个节点值大于根节点，一个节点值小于根节点，
// 说明他们他们一个在根节点的左子树上一个在根节点的右子树上，
// 那么根节点就是他们的最近公共祖先节点（这个性质可以熟记）